package com.kingwood.algorithm.zuochengyun.digui;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/8 14:47
 * @Modified By：
 * @Version 1.0
 */
public class Combinations {
    public static String[] generateAllCombination(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        List<List<Integer>> lists = new ArrayList<>();
        int[] path = new int[len];

        f(arr, 0, path, 0, lists);
        int m = lists.size();
        String[] ans = new String[m];
        int i = 0;

        for (List<Integer> item : lists) {
            ans[i++] = item.stream().map(Object::toString)
                    .collect(Collectors.joining(""));;
        }

        return ans;
    }


    public static void f(int[] nums, int i, int[] path, int size, List<List<Integer>> ans) {
        if (i == nums.length) {
            ArrayList<Integer> cur = new ArrayList<>();
            for (int j = 0; j < size; j++) {
                cur.add(path[j]);
            }
            ans.add(cur);
        } else {
            // 下一组第一个数的位置
            int j = i + 1;
            while (j < nums.length && nums[i] == nums[j]) {
                j++;
            }

            // 当前数要x, 要0个
            f(nums, j, path, size, ans);
            for (; i < j; i++) {
                path[size++] = nums[i];
                f(nums, j, path, size, ans);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        String[] ans = generateAllCombination(arr);
        System.out.println(Arrays.toString(ans));
    }
}
